5621. Найти кратное

 

Имеется n натуральных чисел, среди которых могут быть одинаковые. Выберите из них f (1 ≤ f ≤ n) чисел таким образом, чтобы их сумма делилась на n, то есть существовало такое число k, что

 

n * k = (сумма выбранных чисел)

 

Вход. Первая строка содержит количество чисел n (n ≤ 10000). Каждая из следующих n строк содержит одно число, не превышающее 15000.

 

Выход. Если требуемое подмножество чисел не существует, выведите 0.

В противном случае в первой строке выведите количество выбранных чисел, а затем сами числа (по одному в каждой строке) в произвольном порядке. Если существует несколько подходящих подмножеств, выведите любое из них.

 

Пример входа

Пример выхода

5

1

2

3

4

1

2

2

3

 

 

РЕШЕНИЕ

последовательности, математика

 

Анализ алгоритма

Пусть d1, d2, …, dn – входные числа. Рассмотрим все их частичные суммы

si = d1 + … + di

Так как частичных сумм ровно n, то среди всех значений si mod n обязательно найдутся либо два одинаковых, либо хотя бы одно значение, равное нулю.

Если для некоторых индексов a – 1 < b выполняется

sa-1 mod n = sb mod n,

то сумма da + … + db делится на n.

Следовательно, последовательность чисел da, da + 1, …, db является искомой.

Если же существует такое i, что si mod n = 0, то искомой будет последовательность d1, d2, …, di.

 

Пример

Рассмотрим приведенный пример. Вычислим все частичные суммы:

 

 

 

Искомых наборов имеется несколько. Например:

·        поскольку s1 = s3, то d2 + d3 = 5 делится на 5.

·        поскольку s1 = s5, то d2 + d3 + d4 + d5 = 10 делится на 5.

·        поскольку s3 = s5, то d4 + d5 = 5 делится на 5.

·        поскольку s4 = 0, то d1 + d2 + d3 + d4 = 10 делится на 5.

 

Реализация алгоритма

Входные числа будем хранить в массиве d. Массив r используем для фиксации частичных сумм: если s = d1 + … + di, то присвоим r[s] = i.

 

#define MAX 10100

int d[MAX], r[MAX];

 

Искомым набором чисел, сумма которых делится на n, будут da, da+1, …, db. Выводим их количество b – a + 1, а затем сами числа – по одному на каждой строке.

 

void print(int a, int b)

{

  printf("%d\n",b - a + 1);

  for(int i = a; i <= b; i++)

    printf("%d\n",d[i]);

}

 

Основная часть программы. Инициализируем массив r значением -1 и устанавливаем r[0] = 0, чтобы учесть случай, когда сумма первых i чисел делится на n.

 

memset(r,-1,sizeof(r)); r[0] = 0;

 

Читаем количество чисел n.

 

scanf("%d",&n);

 

Частичные суммы по модулю n вычисляем в переменной sum.

 

sum = 0;

for (i = 1; i <= n; i++)

{

  scanf("%d", &d[i]);

  sum = (sum + d[i]) % n;

 

Если частичная сумма sum встретилась повторно, то выводим искомый набор чисел:

dr[sum] + 1, dr[sum] + 2, …, di

 

  if (r[sum] != -1)

  {

    print(r[sum] + 1, i);

    break;

  }

 

r[sum] хранит первый индекс i, на котором встретилась частичная сумма d1 + … + di с остатком sum при делении на n.

 

  else r[sum] = i;

}